import java.util.Arrays;
import java.util.Stack;

public class redo {

    public static void swap(int []a,int i,int j) {
       int temp = a[i];
       a[i] = a[j];
       a[j] = temp;
    }

    public static boolean greater(int []a,int i,int j) {
        return a[i]>a[j];
    }

    public static void main(String[] args) {
        int []array = {9,5,8,3,4,1,2,7};
        mergeSort1(array);
        System.out.println(Arrays.toString(array));
    }

    //冒泡排序
    public static void bubbleSort(int[] arr) {
        for(int i = 0; i < arr.length - 1; i++) {
            boolean flag = false;
            for(int j = 0;j<arr.length-i-1;j++){
                if(greater(arr,j,j+1)){
                    swap(arr,j,j+1);
                    flag = true;
                }
            }
            if(!flag) {
                break;
            }
        }
    }

    //选择排序
    public static void selectionSort(int[] arr) {
        for(int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            for(int j = i + 1; j < arr.length; j++) {
                if(greater(arr,minIndex,j)) {
                    minIndex = j;
                }
            }
            //避免多余交互
            if(minIndex != i) {
                swap(arr,i,minIndex);
            }
        }
    }

    //选择排序2,同时找最大和最小，复杂度还是O(n^2)
    public static void selectionSort2(int[] arr) {
        int left = 0;
        int right = arr.length - 1;
        while(left < right) {
            int minIndex = left;
            int maxIndex = left;
            for(int i = left+1;i<=right;i++){
                if(greater(arr,minIndex,i)){
                    minIndex = i;
                }
                if(greater(arr,i,maxIndex)){
                    maxIndex = i;
                }
            }
            swap(arr,left,minIndex);
            if(maxIndex==left){
                swap(arr,minIndex,right);
            }else {
                swap(arr,right,maxIndex);
            }
            left++;
            right--;
        }
    }

    //插入排序
    public static void insertionSort(int[] arr) {
        for(int i = 1; i < arr.length; i++) {
            for(int j =i;j>=1;j--){
                if(greater(arr,j-1,j)){
                    swap(arr,j-1,j);
                }else {
                    break;
                }
            }
        }
    }

    //希尔排序
    public static void shellSort(int[] arr) {
        int h = 1;
        while (h < arr.length / 3) {
            h = 3 * h + 1; // Knuth 序列
        }
        while(h >=1) {
            for(int i = h; i < arr.length; i++) {
                for(int j = i;j>=h;j-=h){
                    if(greater(arr,j-h,j)){
                        swap(arr,j-h,j);
                    }else {
                        break;
                    }
                }
            }
           h = h/3;
        }
    }

    //堆排序 时间复杂度O(n*log2n)  对数据不敏感，不管有序无序都是这个复杂度  稳定性：不稳定
    public static void heapSort(int[] arr) {
        createBigHeap(arr);
        int end=arr.length-1;
        while(end>0){
            swap(arr,0,end);
            siftDown(arr,0,end);
            end--;
        }
    }
    //向上调整建堆
    private static void createBigHeap(int[] arr) {
        for(int i = (arr.length-1-1)/2;i>=0;i--){
            siftDown(arr,i,arr.length);
        }
    }
    //向下调整维持大根堆特性
    private static void siftDown(int[] arr, int parent,int len) {
        int child = parent*2+1;
        while(child < len){
            if(child+1<len&&arr[child]<arr[child+1]){
                child++;
            }
            if(arr[child]>arr[parent]){
                swap(arr,parent,child);
                parent = child;
                child = parent*2+1;
            }else {
                break;
            }
        }
    }



    //快速排序（Hoare版)
    public static void quickSort(int[] arr) {
        quick(arr,0,arr.length-1);
    }
    private static void quick(int[]arr,int start,int end){
        if(start>=end){
            return;
        }
        int pivot = parttion(arr,start,end);
        //分别递归左树和右树
        quick(arr,start,pivot-1);//左树

        quick(arr,pivot+1,end);//右树

    }

    private static int parttion(int[] arr,int left,int right){
        int i = left;
        int tmp = arr[left];
        while(left<right){
            //下面的条件中一定要有等于，不然会容易right和left不动，然后
            //又满足大循环条件，无限无意义交互
            while (arr[right]>=tmp && left<right) {
                right--;
            }
            while (arr[left]<=tmp && left<right) {
                left++;
            }
            swap(arr,left,right);
        }
        swap(arr,i,left);
        return left;//返回新的基准值下标
    }


    //快速排序（挖坑法）
    public static void quickSort2(int[] arr) {
        quick2(arr,0,arr.length-1);
    }
    private static void quick2(int[] arr,int left,int right) {
        if(left>=right){
            return;
        }
        int pivot = arr[left];
        int l =left;
        int r = right;
        while(l<r){
            //1.从右向左找比基准小的数
            while(l<r&&arr[r]>=pivot){
                r--;
            }
            arr[l]=arr[r];//右侧挖坑，填到左侧

            //2.从左向右找比基准大的数
            while(l<r&&arr[l]<=pivot){
                l++;
            }
            arr[r]=arr[l];//左侧挖坑，填到右侧
        }
        //3.基准值填入最终位置
        arr[l]=pivot;

        //递归处理左右子树
        quick2(arr,left,l-1);
        quick2(arr,l+1,right);
    }


    //非递归快速排序（借助栈来成对匹配start和end）
    public static void quickSort3(int[] arr) {
        int start = 0;
        int end = arr.length-1;
        int pivot = parttion(arr,start,end);
        Stack<Integer> stack = new Stack<Integer>();
        if(pivot<end-1){
            stack.push(pivot+1);
            stack.push(end);
        }
        if(pivot>start+1){
            stack.push(start);
            stack.push(pivot-1);
        }
        while (!stack.isEmpty()){
            end = stack.pop();
            start = stack.pop();
            pivot = parttion(arr,start,end);
            if(pivot<end-1){
                stack.push(pivot+1);
                stack.push(end);
            }
            if(pivot>start+1){
                stack.push(start);
                stack.push(pivot-1);
            }
        }
    }

    //归并排序
    public static void mergeSort(int[] arr) {
        mergeSortFunc(arr,0,arr.length-1);
    }
    //合并
    private static void merge(int[] arr, int left, int mid, int right) {
        int s1 = left;
        int s2 = mid + 1;
        int e1 = mid;
        int e2 = right;
        int[] tmpArr = new int[right - left + 1];
        int k =0;
        while (s1<=e1 && s2<=e2) {
            if(arr[s1]<arr[s2]){
                tmpArr[k++] = arr[s1++];
            }else {
                tmpArr[k++] = arr[s2++];
            }
        }
        while (s1<=e1) {
            tmpArr[k++] = arr[s1++];
        }
        while (s2<=e2) {
            tmpArr[k++] = arr[s2++];
        }

        for (int i = 0; i < tmpArr.length; i++) {
            arr[left + i] = tmpArr[i];
        }

    }
    //递归划分
    private static void mergeSortFunc(int[] arr, int left, int right) {
        if(left>=right){
            return;
        }
        int mid = (left + right)/2;
        mergeSortFunc(arr, left, mid);
        mergeSortFunc(arr, mid+1, right);

        merge(arr, left, mid, right);
    }


    //归并排序（非递归）
    private static void mergeSort1(int[] arr) {
        int gap = 1;
        while (gap < arr.length) {
            for(int i =0;i<arr.length;i=i+2*gap){
                int left = i;
                int mid = i+gap-1;
                int right = mid+gap;
                if(mid>=arr.length){
                    //纠正避免越界
                    mid = arr.length-1;
                }
                if(right>=arr.length){
                    //纠正
                    right = arr.length-1;
                }
                merge(arr,left,mid,right);
            }
            gap *= 2;
        }

    }




}
